{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Diameter of N-Ary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: diameter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #N 叉树的直径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一棵 N 叉树的根节点&nbsp;<code>root</code>&nbsp;，计算这棵树的直径长度。</p>\n",
    "\n",
    "<p>N 叉树的直径指的是树中任意两个节点间路径中<strong> 最长 </strong>路径的长度。这条路径可能经过根节点，也可能不经过根节点。</p>\n",
    "\n",
    "<p><em>（N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔）</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/07/19/sample_2_1897.png\" style=\"height:173px; width:324px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,3,2,4,null,5,6]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>直径如图中红线所示。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/07/19/sample_1_1897.png\" style=\"height:246px; width:253px\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,null,3,4,null,5,null,6]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/07/19/sample_3_1897.png\" style=\"height:326px; width:369px\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]\n",
    "<strong>输出:</strong> 7\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>N 叉树的深度小于或等于&nbsp;<code>1000</code>&nbsp;。</li>\n",
    "\t<li>节点的总个数在&nbsp;<code>[0,&nbsp;10^4]</code>&nbsp;间。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [diameter-of-n-ary-tree](https://leetcode.cn/problems/diameter-of-n-ary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [diameter-of-n-ary-tree](https://leetcode.cn/problems/diameter-of-n-ary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,3,2,4,null,5,6]', '[1,null,2,null,3,4,null,5,null,6]', '[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        for mask in range(3, 1 << n):  # 二进制枚举所有集合\n",
    "            if mask.bit_count() < 2:  # 至少要2个点\n",
    "                continue\n",
    "\n",
    "            vis = diameter = 0\n",
    "\n",
    "            def dfs(x: int) -> int:  # 从x点出发，求包含x的子树的直径\n",
    "                nonlocal vis, diameter\n",
    "                vis |= 1 << x  # 标识访问\n",
    "                mx_len = 0\n",
    "                for y in g[x]:\n",
    "                    if (1 << y) & mask and (1 << y) & vis == 0:  # y在mask里面但是还未访问过\n",
    "                        ml = dfs(y) + 1\n",
    "                        diameter = max(diameter, mx_len + ml)\n",
    "                        mx_len = max(mx_len, ml)\n",
    "                return mx_len\n",
    "\n",
    "            t = mask\n",
    "            i = 0\n",
    "            while t:  # 从一个在 mask 中的点开始递归\n",
    "                if (t >> i) & 1:\n",
    "                    break\n",
    "                i += 1\n",
    "            dfs(i)\n",
    "            if vis == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1) # 建树，编号改为从0开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        for mask in range(3, 1 << n): # 二进制枚举\n",
    "            if (mask & (mask - 1)) == 0: #需要至少两个点\n",
    "                continue\n",
    "            vis = diameter = 0 # 求树的直径\n",
    "            def dfs(x:int) -> int:\n",
    "                nonlocal vis, diameter\n",
    "                vis |= 1 << x #标记x访问过\n",
    "                max_len = 0\n",
    "                for y in g[x]:\n",
    "                    if (vis >> y & 1) == 0 and mask >> y & 1: # y没有访问过， 且在mask中\n",
    "                        ml = dfs(y) + 1\n",
    "                        diameter = max(diameter, max_len + ml)\n",
    "                        max_len = max(max_len, ml)\n",
    "                return max_len\n",
    "            dfs(mask.bit_length() - 1) # 从一个在mask中的点开始递归\n",
    "            if vis == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(n)]                              # 建图\n",
    "        for u, v in edges:\n",
    "            graph[u - 1].append(v - 1)\n",
    "            graph[v - 1].append(u - 1)\n",
    "\n",
    "        def dfs(mask, u):\n",
    "            nonlocal visited, diameter\n",
    "            visited |= 1 << u                                       # 标记 u 访问过\n",
    "            u_len = 0                                               # u 节点的最大路径长度\n",
    "            for v in graph[u]:                                      # 遍历 u 节点的相邻节点\n",
    "                if (visited >> v) & 1 == 0 and mask >> v & 1:       # v 没有访问过，且在子集中\n",
    "                    v_len = dfs(mask, v)                            # 相邻节点的最大路径长度\n",
    "                    diameter = max(diameter, u_len + v_len + 1)     # 维护最大路径长度\n",
    "                    u_len = max(u_len, v_len + 1)                   # 更新 u 节点的最大路径长度\n",
    "            return u_len\n",
    "        \n",
    "        ans = [0 for _ in range(n - 1)]\n",
    "\n",
    "        for mask in range(3, 1 << n):                               # 二进制枚举子集\n",
    "            if mask & (mask - 1) == 0:                              # 子集至少需要两个点\n",
    "                continue\n",
    "            visited = 0\n",
    "            diameter = 0\n",
    "            u = mask.bit_length() - 1        \n",
    "            dfs(mask, u)                                            # 在子集 mask 中递归求树的直径\n",
    "            if visited == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        for mask in range(3, 1 << n):\n",
    "            if (mask & (mask - 1)) == 0:\n",
    "                continue;\n",
    "            vis = diameter = 0\n",
    "            def dfs(x: int) -> int:\n",
    "                nonlocal vis, diameter\n",
    "                vis |= 1 << x\n",
    "                max_len = 0\n",
    "                for y in g[x]:\n",
    "                    if (vis >> y & 1) == 0 and mask >> y & 1:\n",
    "                        ml = dfs(y) + 1\n",
    "                        diameter = max(diameter, max_len + ml)\n",
    "                        max_len = max(max_len, ml)\n",
    "                return max_len\n",
    "            dfs(mask.bit_length() - 1)\n",
    "            if vis == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                len = dfs(y) + 1\n",
    "                                diameter = max(diameter, len + max_len)\n",
    "                                max_len = max(max_len, len)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter-1] += 1\n",
    "                return\n",
    "\n",
    "            f(i+1)\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "        \n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # n个节点的树，返回ans[i]，节点间距离为i的节点对数\n",
    "\n",
    "        g = [[] for _ in range(n)]      # 建树\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)      # 编号改为从0开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "\n",
    "        def f(i: int)-> None: # 子树枚举\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "\n",
    "                    def dfs(x: int)-> int:  # 求子树的直径\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            f(i + 1) # 不选城市i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False   # 回复现场\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b:\n",
    "                        continue\n",
    "                    # 求树直径\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            f(i+1)\n",
    "\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "        \n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1) # 编号改为从0开始\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                visited = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        visited[x] = b\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not visited[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(ml, max_len)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and visited == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return \n",
    "            f(i + 1)\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False\n",
    "        f(0)\n",
    "        return ans \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            tree[u-1].append(v-1)\n",
    "            tree[v-1].append(u-1)\n",
    "\n",
    "        ans = [0] * (n-1)\n",
    "        in_set = [False] * n\n",
    "        \n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    #find tree diameter\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in tree[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, ml + max_len)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len \n",
    "                    \n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return \n",
    "            \n",
    "            f(i+1)\n",
    "\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "        f(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x-1].append(y-1)\n",
    "            g[y-1].append(x-1)\n",
    "\n",
    "        ans = [0] * (n-1)\n",
    "        in_set = [False] * n\n",
    "        def f(i):\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v,b in enumerate(in_set):\n",
    "                    if not b:\n",
    "                        continue\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                cur_len = dfs(y) + 1\n",
    "                                diameter = max(diameter, cur_len + max_len)\n",
    "                                max_len = max(max_len, cur_len)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "        \n",
    "            f(i+1)\n",
    "\n",
    "            in_set[i] = True\n",
    "            f(i+1)\n",
    "            in_set[i] = False\n",
    "        f(0)\n",
    "        return ans\n",
    "\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "\n",
    "        # 标记是否选择该节点\n",
    "        in_set = [False] * n  \n",
    "        \n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0  # 直径\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    \n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选择节点i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选择节点i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False\n",
    "    \n",
    "        f(0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    做本题需要弄清楚两点：\n",
    "    1.最大距离就是求一棵树的最大直径（最大的子树边数，不是节点数）\n",
    "    2.如果把所有的合法子树都判断好\n",
    "    第一点比较容易，可以参考：https://leetcode.cn/problems/tree-diameter/\n",
    "    第二点根据题目给出的信息节点数1 - n，n的范围在2 - 15，所以可以用状态压缩，用整形mask表示子树中包含有哪些\n",
    "    节点，对应位置为1表示存在对应下标值的节点，0表示不存在对应下标值的节点\n",
    "    '''\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u - 1].append(v - 1)\n",
    "            graph[v - 1].append(u - 1)\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "        '''\n",
    "        外层枚举所有的节点组合，要有直径最少要有2个节点，对应mask从3开始\n",
    "        '''\n",
    "        for mask in range(3, 1 << n):\n",
    "            '''\n",
    "            如果有只有一个1，那么mask & mask - 1一定是0，这种方式能过滤掉只有一个1的情况\n",
    "            '''\n",
    "            if not (mask & (mask - 1)):\n",
    "                continue\n",
    "\n",
    "            vis, diameter = 0, 0\n",
    "            '''\n",
    "            以u节点为根节点，计算该子树的最长直径，此时可能mask对应的节点并不能组成一颗合法的树，\n",
    "            比如例1中只选择了1、3、4三个节点，对于这种情况，其实从任意一点往下走，都不可能走完整颗\n",
    "            树，所以用变量vis记录走过的所有节点，最终vis == mask说明当前选择的树是联通的\n",
    "            '''\n",
    "            def helper(u):\n",
    "                nonlocal vis, mask, diameter\n",
    "                vis |= 1 << u\n",
    "                mx, smx = 0, 0\n",
    "                for v in graph[u]:\n",
    "                    if vis & (1 << v) or not (mask & (1 << v)):\n",
    "                        continue\n",
    "                    res = helper(v) + 1\n",
    "                    if res > mx:\n",
    "                        smx = mx\n",
    "                        mx = res \n",
    "                    elif res > smx:\n",
    "                        smx = res\n",
    "                    \n",
    "                    diameter = max(diameter, mx + smx)\n",
    "                return mx\n",
    "            '''\n",
    "            bit_length()表示二进制第一个1是第几位数，从低位到高位算（右到左），减一就等于第一位从0开始的下标，\n",
    "            正好就是选择了一个节点\n",
    "            '''\n",
    "            helper(mask.bit_length() - 1)\n",
    "            if vis == mask:\n",
    "                ans[diameter - 1] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u - 1].append(v - 1)\n",
    "            graph[v - 1].append(u - 1)\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "\n",
    "        for mask in range(3, 1 << n):\n",
    "            if not (mask & (mask - 1)):\n",
    "                continue\n",
    "\n",
    "            vis, diameter = 0, 0\n",
    "\n",
    "            def helper(u):\n",
    "                nonlocal vis, mask, diameter\n",
    "                vis |= 1 << u\n",
    "                mx, smx = 0, 0\n",
    "                for v in graph[u]:\n",
    "                    if vis & (1 << v) or not (mask & (1 << v)):\n",
    "                        continue\n",
    "                    res = helper(v) + 1\n",
    "                    if res > mx:\n",
    "                        smx = mx\n",
    "                        mx = res \n",
    "                    elif res > smx:\n",
    "                        smx = res\n",
    "                    \n",
    "                    diameter = max(diameter, mx + smx + 1)\n",
    "                return mx\n",
    "            \n",
    "            helper(mask.bit_length() - 1)\n",
    "            if vis == mask and diameter:\n",
    "                ans[diameter - 2] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            graph[u - 1].append(v - 1)\n",
    "            graph[v - 1].append(u - 1)\n",
    "        \n",
    "        ans = [0] * (n - 1)\n",
    "\n",
    "        for mask in range(3, 1 << n):\n",
    "            if not (mask & (mask - 1)):\n",
    "                continue\n",
    "\n",
    "            vis, diameter = 0, 0\n",
    "\n",
    "            def helper(u):\n",
    "                nonlocal vis, mask, diameter\n",
    "                vis |= 1 << u\n",
    "                mx, smx = 0, 0\n",
    "                for v in graph[u]:\n",
    "                    if vis & (1 << v) or not (mask & (1 << v)):\n",
    "                        continue\n",
    "                    res = helper(v) + 1\n",
    "                    if res > mx:\n",
    "                        smx = mx\n",
    "                        mx = res \n",
    "                    elif res > smx:\n",
    "                        smx = res\n",
    "                    \n",
    "                    diameter = max(diameter, mx + smx + 1)\n",
    "                return mx\n",
    "            \n",
    "            helper(mask.bit_length() - 1)\n",
    "            if vis == mask:\n",
    "                ans[diameter - 2] += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a-1].append(b-1)\n",
    "            g[b-1].append(a-1)\n",
    "        ans = [0] * (n - 1)\n",
    "        def dfs(u):\n",
    "            nonlocal diameter, vis\n",
    "            vis |= 1 << u\n",
    "            maxLen = 0\n",
    "            for v in g[u]:\n",
    "                if (vis >> v & 1) == 0 and (mask >> v & 1) == 1:\n",
    "                    len = dfs(v) + 1\n",
    "                    diameter = max(diameter, maxLen + len)\n",
    "                    maxLen = max(maxLen, len)\n",
    "            return maxLen\n",
    "\n",
    "        for mask in range(3, 1 << n):\n",
    "            if mask & (mask - 1) == 0: continue\n",
    "            vis = 0\n",
    "            diameter = 0\n",
    "            u = mask.bit_length() - 1\n",
    "            dfs(u)\n",
    "            if vis == mask:\n",
    "                ans[diameter-1] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        res = [0] * (n - 1)\n",
    "\n",
    "        inset = [False] * n\n",
    "\n",
    "        def f(i):\n",
    "\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "\n",
    "                for v, b in enumerate(inset):\n",
    "                    if not b: continue\n",
    "\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "\n",
    "                        vis[x] = True\n",
    "\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and inset[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == inset:\n",
    "                    res[diameter - 1] += 1\n",
    "                return\n",
    "            f(i + 1)\n",
    "\n",
    "            inset[i] = True\n",
    "            f(i + 1)\n",
    "            inset[i] = False\n",
    "        f(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        res = [0] * (n - 1)\n",
    "\n",
    "        inset = [False] * n\n",
    "\n",
    "        def f(i):\n",
    "\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "\n",
    "                for v, b in enumerate(inset):\n",
    "                    if not b: continue\n",
    "\n",
    "                    def dfs(x):\n",
    "                        nonlocal diameter\n",
    "\n",
    "                        vis[x] = True\n",
    "\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and inset[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == inset:\n",
    "                    res[diameter - 1] += 1\n",
    "                return\n",
    "            f(i + 1)\n",
    "\n",
    "            inset[i] = True\n",
    "            f(i + 1)\n",
    "            inset[i] = False\n",
    "        f(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class TreeDiameter:\n",
    "    def __init__(self, dct):\n",
    "        self.n = len(dct)\n",
    "        self.dct = dct\n",
    "        return\n",
    "    \n",
    "    def get_bfs_dis(self, root):\n",
    "        dis = [inf] * self.n\n",
    "        stack = [root]\n",
    "        dis[root] = 0\n",
    "        parent = [-1] * self.n\n",
    "        while stack:\n",
    "            i = stack.pop()\n",
    "            for j, w in self.dct[i]:\n",
    "                if j != parent[i]:\n",
    "                    parent[j] = i\n",
    "                    dis[j] = dis[i] + w\n",
    "                    stack.append(j)\n",
    "        return dis, parent\n",
    "    \n",
    "    def get_diameter_info(self) -> (int, int, List[int], any):\n",
    "        # get tree diameter detail by bfs twice\n",
    "        dis, _ = self.get_bfs_dis(0)\n",
    "        x = dis.index(max(dis))\n",
    "        dis, parent = self.get_bfs_dis(x)\n",
    "        y = dis.index(max(dis))\n",
    "        path = [y]\n",
    "        while path[-1] != x:\n",
    "            path.append(parent[path[-1]])\n",
    "        path.reverse()\n",
    "        return x, y, path, dis[y]\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 模板：枚举子集使用并查集判断连通性再计算树的直径\n",
    "        ans = [0] * n\n",
    "        for state in range(1, 1 << n):\n",
    "            node = [i for i in range(n) if state & (1 << i)]\n",
    "            ind = {num: i for i, num in enumerate(node)}\n",
    "            m = len(node)\n",
    "            dct = [[] for _ in range(m)]\n",
    "            uf = UnionFind(m)\n",
    "            for u, v in edges:\n",
    "                u -= 1\n",
    "                v -= 1\n",
    "                if u in ind and v in ind:\n",
    "                    dct[ind[u]].append([ind[v], 1])\n",
    "                    dct[ind[v]].append([ind[u], 1])\n",
    "                    uf.union(ind[u], ind[v])\n",
    "            if uf.part != 1:\n",
    "                continue\n",
    "            tree = TreeDiameter(dct)\n",
    "            ans[tree.get_diameter_info()[-1]] += 1\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * (n-1)\n",
    "        g = defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            if not path:\n",
    "                return\n",
    "            dia = 1\n",
    "            # f(v) to get the diameter of a tree\n",
    "            def f(u):\n",
    "                nonlocal dia\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        dia = max(dia, maxv+ cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            f(path[0])\n",
    "\n",
    "            if vis == set(path)  and dia - 1 >= 1:   \n",
    "                ans[dia-2] +=1\n",
    "        def dfs(i, pre):\n",
    "            if i==n:\n",
    "                check(pre)\n",
    "                return\n",
    "            dfs(i+1,pre)\n",
    "            dfs(i+1,pre+[i])\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 建树\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)  # 编号改为从 0 开始\n",
    "\n",
    "        ans = [0] * (n - 1)\n",
    "        in_set = [False] * n\n",
    "        def f(i: int) -> None:\n",
    "            if i == n:\n",
    "                vis = [False] * n\n",
    "                diameter = 0\n",
    "                for v, b in enumerate(in_set):\n",
    "                    if not b: continue\n",
    "                    # 求树的直径\n",
    "                    def dfs(x: int) -> int:\n",
    "                        nonlocal diameter\n",
    "                        vis[x] = True\n",
    "                        max_len = 0\n",
    "                        for y in g[x]:\n",
    "                            if not vis[y] and in_set[y]:\n",
    "                                ml = dfs(y) + 1\n",
    "                                diameter = max(diameter, max_len + ml)\n",
    "                                max_len = max(max_len, ml)\n",
    "                        return max_len\n",
    "                    dfs(v)\n",
    "                    break\n",
    "                if diameter and vis == in_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "            \n",
    "            # 不选城市 i\n",
    "            f(i + 1)\n",
    "\n",
    "            # 选城市  i\n",
    "            in_set[i] = True\n",
    "            f(i + 1)\n",
    "            in_set[i] = False  # 恢复现场\n",
    "        f(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for v in edges:\n",
    "            g[v[0] - 1].append(v[1] - 1)\n",
    "            g[v[1] - 1].append(v[0] - 1)\n",
    "        ans = [0] * (n - 1)\n",
    "\n",
    "        is_set = [False] * n\n",
    "\n",
    "        def dfs(i: int) -> None:\n",
    "            if i == n:\n",
    "                is_vis = [False] * n\n",
    "                diameter = 0\n",
    "\n",
    "                for i, v in enumerate(is_set):\n",
    "                    if not v:\n",
    "                        continue\n",
    "\n",
    "                    def f(i: int) -> int:\n",
    "                        pre_max = 0\n",
    "                        is_vis[i] = True\n",
    "                        for j in g[i]:\n",
    "                            if not is_vis[j] and is_set[j]:\n",
    "                                cur_l = f(j) + 1\n",
    "                                nonlocal diameter\n",
    "                                diameter = max(cur_l + pre_max, diameter)\n",
    "                                pre_max = max(cur_l, pre_max)\n",
    "\n",
    "                        return pre_max\n",
    "\n",
    "                    f(i)\n",
    "                    break\n",
    "\n",
    "                if diameter > 0 and is_vis == is_set:\n",
    "                    ans[diameter - 1] += 1\n",
    "                return\n",
    "\n",
    "            dfs(i + 1)\n",
    "\n",
    "            is_set[i] = True\n",
    "            dfs(i + 1)\n",
    "            is_set[i] = False\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class TreeDiameter:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def build(dct: List[List[int]]) -> (int, int, List[int], any):\n",
    "        # get tree diameter detail by bfs twice\n",
    "        n = len(dct)\n",
    "        x = y = 0\n",
    "        parent = [-1] * n\n",
    "        dis = [inf] * n\n",
    "        for _ in range(2):\n",
    "            x = y\n",
    "            dis = [inf] * n\n",
    "            stack = [x]\n",
    "            dis[x] = 0\n",
    "            parent = [-1] * n\n",
    "            while stack:\n",
    "                i = stack.pop()\n",
    "                for j, w in dct[i]:\n",
    "                    if j != parent[i]:\n",
    "                        parent[j] = i\n",
    "                        dis[j] = dis[i] + w\n",
    "                        stack.append(j)\n",
    "            y = dis.index(max(dis))\n",
    "\n",
    "        path = [y]\n",
    "        while path[-1] != x:\n",
    "            path.append(parent[path[-1]])\n",
    "        path.reverse()\n",
    "        return x, y, path, dis[y]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        # 模板：枚举子集使用并查集判断连通性再计算树的直径\n",
    "        ans = [0] * n\n",
    "        for state in range(1, 1 << n):\n",
    "            node = [i for i in range(n) if state & (1 << i)]\n",
    "            ind = {num: i for i, num in enumerate(node)}\n",
    "            m = len(node)\n",
    "            dct = [[] for _ in range(m)]\n",
    "            uf = UnionFind(m)\n",
    "            for u, v in edges:\n",
    "                u -= 1\n",
    "                v -= 1\n",
    "                if u in ind and v in ind:\n",
    "                    dct[ind[u]].append([ind[v], 1])\n",
    "                    dct[ind[v]].append([ind[u], 1])\n",
    "                    uf.union(ind[u], ind[v])\n",
    "            if uf.part != 1:\n",
    "                continue\n",
    "            ans[TreeDiameter().build(dct)[-1]] += 1\n",
    "        return ans[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:\n",
    "        ans = [0] * (n-1)\n",
    "        g =defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        def check(path):\n",
    "            vis = set()\n",
    "            if not path:\n",
    "                return \n",
    "            # get the diameter of a tree\n",
    "            dia = 1\n",
    "            def f(u):\n",
    "                nonlocal dia\n",
    "                vis.add(u)\n",
    "                maxv = 0\n",
    "                for v in g[u]:\n",
    "                    if v not in vis and v in path:\n",
    "                        cur = f(v)\n",
    "                        dia = max(dia, maxv + cur + 1)\n",
    "                        maxv = max(maxv, cur)\n",
    "                return maxv + 1\n",
    "            f(path[0])    \n",
    "            if vis == set(path) and dia -1 >= 1:\n",
    "                ans[dia-2] +=1\n",
    "        def dfs(i,pre):\n",
    "            if i ==n:\n",
    "                check(pre)\n",
    "                return \n",
    "            dfs(i+1, pre)\n",
    "            dfs(i+1, pre+[i])\n",
    "        dfs(0,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            nonlocal res\n",
    "            # left length\n",
    "            left = dfs(node.left)\n",
    "            # right length\n",
    "            right = dfs(node.right)\n",
    "            res = max(res, left+right)\n",
    "            return max(left, right)+1\n",
    "        dfs(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.res = 0\n",
    "        self.helper(root)\n",
    "        return self.res\n",
    "    \n",
    "    def helper(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        # self.res.append(root)\n",
    "        # self.helper\n",
    "        left = self.helper(root.left)\n",
    "        right = self.helper(root.right)\n",
    "        self.res = max(self.res, left + right)\n",
    "        return 1 + max(left, right)\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param root: a root of binary tree\n",
    "    @return: return a integer\n",
    "    \"\"\"\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        # write your code here\n",
    "        l, m = self.find_depth(root)\n",
    "        return m\n",
    "\n",
    "    def find_depth(self, root):\n",
    "        if not root:\n",
    "            return 0, 0\n",
    "        l, m1 = self.find_depth(root.left) \n",
    "        r, m2 = self.find_depth(root.right) \n",
    "        return max(l, r) + 1 , max(l + r, m1, m2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:        \n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.ans = 1  # 只是方便处理root为None的情况\n",
    "        def depth(node):\n",
    "            if not node: return 0\n",
    "            L = depth(node.left)\n",
    "            R = depth(node.right)\n",
    "            self.ans = max(self.ans, L+R+1)\n",
    "            return max(L, R) + 1\n",
    "\n",
    "        depth(root)\n",
    "        return self.ans - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return 0\n",
    "        if root.left==None and root.right==None:\n",
    "            return 0\n",
    "        heights = []\n",
    "        def twoHeight(root):\n",
    "            if root.left==None and root.right==None:\n",
    "                heights.append(1)\n",
    "                return 1\n",
    "            hl,hr=0,0\n",
    "            if root.left:\n",
    "                hl = twoHeight(root.left)\n",
    "            if root.right:\n",
    "                hr = twoHeight(root.right)\n",
    "            heights.append(hl+hr)\n",
    "            return max(hl,hr)+1\n",
    "        twoHeight(root)\n",
    "        return max(heights)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return 0\n",
    "        def tree_height_and_diameter(root):\n",
    "            if not root.left and not root.right:\n",
    "                return [1, 0]\n",
    "            l = [0, 0]\n",
    "            r = [0, 0]\n",
    "            if root.left:\n",
    "                l = tree_height_and_diameter(root.left)\n",
    "            if root.right:\n",
    "                r = tree_height_and_diameter(root.right)\n",
    "            height = max(l[0], r[0]) + 1\n",
    "            diameter = 0\n",
    "            if not root.right:\n",
    "                diameter = max(l[1], height - 1)\n",
    "            elif not root.left:\n",
    "                diameter = max(r[1], height - 1)\n",
    "            else:\n",
    "                diameter = max(l[1], r[1], l[0] + r[0])\n",
    "            return [height, diameter]\n",
    "        return tree_height_and_diameter(root)[1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        \n",
    "        def maxDepth(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            L = maxDepth(node.left)\n",
    "            R = maxDepth(node.right)\n",
    "            self.res = max(self.res, L + R)\n",
    "            return max(L, R) + 1\n",
    "        \n",
    "        maxDepth(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        # 这种题的解法一般就是从根节点开始递归\n",
    "        # 你要分析呀，根节点为root的树的直径可能是什么？无非就是两种情况\n",
    "        # 直径经过根节点，那么直径就是左子树深度＋右子树深度，不经过根节点，那么直径就是左子树直径或者右子树直径\n",
    "        # 最终结果就是这三者的最大值\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        res = self.depth(root.left) + self.depth(root.right)\n",
    "        return max(res, self.diameterOfBinaryTree(root.left), self.diameterOfBinaryTree(root.right))\n",
    "        \n",
    "    def depth(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        left_dep = self.depth(root.left)\n",
    "        right_dep = self.depth(root.right)\n",
    "        \n",
    "        return max(left_dep, right_dep) + 1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import collections\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # [4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]\n",
    "        if not root: return 0\n",
    "        def hello(root,m):\n",
    "            if not root:return m\n",
    "            return max(hello(root.left,m+1),hello(root.right,m+1))\n",
    "        def new(root):\n",
    "            return hello(root.left,0)+hello(root.right,0)\n",
    "        \n",
    "        return max(new(root),self.diameterOfBinaryTree(root.left),self.diameterOfBinaryTree(root.right))\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def get_root(self, root):\n",
    "        stack = [root]\n",
    "        aux_stack = []\n",
    "        while stack:\n",
    "            for node in stack:\n",
    "                if node.left and node.right:\n",
    "                    return node \n",
    "                if node.left:\n",
    "                    aux_stack.append(node.left)\n",
    "                if node.right:\n",
    "                    aux_stack.append(node.right)\n",
    "            stack = aux_stack\n",
    "            aux_stack = []\n",
    "        return None\n",
    "\n",
    "\n",
    "    def get_depth(self, root):\n",
    "        depth = -1 \n",
    "        if root is None:\n",
    "            return depth\n",
    "        stack = [root]\n",
    "        aux_stack = []\n",
    "        while stack:\n",
    "            depth += 1 \n",
    "            for node in stack:\n",
    "                if node.left:\n",
    "                    aux_stack.append(node.left)\n",
    "                if node.right:\n",
    "                    aux_stack.append(node.right)\n",
    "            stack = aux_stack\n",
    "            aux_stack = []\n",
    "        return depth \n",
    "\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        elif not root.left and not root.right:\n",
    "            return 0\n",
    "        res = 0\n",
    "        stack = [root]\n",
    "        aux_stack = []\n",
    "        while stack:\n",
    "            for node in stack:\n",
    "                x = -1\n",
    "                y = -1 \n",
    "                if node.left:\n",
    "                    x = self.get_depth(node.left)\n",
    "                    aux_stack.append(node.left)\n",
    "                if node.right:\n",
    "                    y = self.get_depth(node.right)\n",
    "                    aux_stack.append(node.right)\n",
    "                res = max(x + y + 2, res)\n",
    "            stack = aux_stack\n",
    "            aux_stack = []\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        #寻找每一颗树的直径，为左子树的长度+右子树的长度+1. 最后将最大的直径返回\n",
    "        if not root:\n",
    "            return 0\n",
    "        length_list = []\n",
    "        queue = []\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)  \n",
    "            length_list.append(self.findHeight(node.right) + self.findHeight(node.left))\n",
    "\n",
    "        return max(length_list)\n",
    "    def findHeight(self, root):\n",
    "        if not TreeNode:\n",
    "            return 0\n",
    "        queue = []          #这里的queue是个栈\n",
    "        queue.append((1,root))\n",
    "        height = 0\n",
    "        while queue:\n",
    "            curre_height, node = queue.pop()\n",
    "            if node is not None:\n",
    "                height = max(height, curre_height)\n",
    "                queue.append((curre_height + 1, node.left))\n",
    "                queue.append((curre_height + 1, node.right))\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    def __init__(self):\n",
    "        self.diameter=0\n",
    "\n",
    "    def lgst(self,root:TreeNode)->int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            l=self.lgst(root.left)\n",
    "            r=self.lgst(root.right)\n",
    "            self.diameter=max(self.diameter,l+r)\n",
    "        return max(l,r)+1\n",
    "\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.lgst(root)\n",
    "        return self.diameter\n",
    "        '''\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        dia=0\n",
    "        fg=[]#[是否右孩子标志，左边深度]\n",
    "        st=[]\n",
    "        node=root\n",
    "        lastr=0\n",
    "        while st or node:\n",
    "            if node:\n",
    "                st.append(node)\n",
    "                fg.append([1,0])\n",
    "                node=node.left\n",
    "            elif fg[-1][0]:\n",
    "                fg[-1][0]=0\n",
    "                fg[-1][1]=lastr\n",
    "                lastr=0\n",
    "                node=st[-1].right\n",
    "            else:\n",
    "                dia=max(dia,lastr+fg[-1][1])\n",
    "                lastr=max(lastr,fg[-1][1])+1\n",
    "                fg.pop()\n",
    "                st.pop()\n",
    "        return dia\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        def height(node):\n",
    "            if not node: return 0\n",
    "            queue = [node]\n",
    "            height = 0\n",
    "            while queue:\n",
    "                height += 1\n",
    "                for i in range(len(queue)):\n",
    "                    n = queue.pop(0)\n",
    "                    if n.left: queue.append(n.left)\n",
    "                    if n.right: queue.append(n.right)\n",
    "            return height\n",
    "\n",
    "        if not root: return 0\n",
    "        res = 0\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            n = queue.pop()\n",
    "            res = max(res, height(n.left)+height(n.right))\n",
    "            if n.left: queue.append(n.left)\n",
    "            if n.right: queue.append(n.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        def maxdepth(root):\n",
    "            res = 0\n",
    "            current_nodes = [root]\n",
    "            while current_nodes:\n",
    "                res += 1\n",
    "                next_nodes = []\n",
    "                for node in current_nodes:\n",
    "                    if node.left:\n",
    "                        next_nodes.append(node.left)\n",
    "                    if node.right:\n",
    "                        next_nodes.append(node.right)\n",
    "                current_nodes = next_nodes\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        if not root:\n",
    "            return 0\n",
    "        current_nodes = [root]\n",
    "        res = float('-inf')\n",
    "        while current_nodes:\n",
    "            next_nodes = []\n",
    "            for node in current_nodes:\n",
    "                if node.left:\n",
    "                    num_left = maxdepth(node.left)\n",
    "                    next_nodes.append(node.left)\n",
    "                else:\n",
    "                    num_left = 0\n",
    "                if node.right:\n",
    "                    num_right = maxdepth(node.right)\n",
    "                    next_nodes.append(node.right)\n",
    "                else:\n",
    "                    num_right = 0\n",
    "                tmp = abs(num_left + num_right)\n",
    "                res = max(res, tmp)\n",
    "            current_nodes = next_nodes\n",
    "        \n",
    "\n",
    "        return res\n",
    "            \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        def maxdepth(root):\n",
    "            res = 0\n",
    "            current_nodes = [root]\n",
    "            while current_nodes:\n",
    "                res += 1\n",
    "                next_nodes = []\n",
    "                for node in current_nodes:\n",
    "                    if node.left:\n",
    "                        next_nodes.append(node.left)\n",
    "                    if node.right:\n",
    "                        next_nodes.append(node.right)\n",
    "                current_nodes = next_nodes\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        if not root:\n",
    "            return 0\n",
    "        current_nodes = [root]\n",
    "        res = float('-inf')\n",
    "        while current_nodes:\n",
    "            next_nodes = []\n",
    "            for node in current_nodes:\n",
    "                if node.left:\n",
    "                    num_left = maxdepth(node.left)\n",
    "                    next_nodes.append(node.left)\n",
    "                else:\n",
    "                    num_left = 0\n",
    "                if node.right:\n",
    "                    num_right = maxdepth(node.right)\n",
    "                    next_nodes.append(node.right)\n",
    "                else:\n",
    "                    num_right = 0\n",
    "                tmp = num_left + num_right\n",
    "                res = max(res, tmp)\n",
    "            current_nodes = next_nodes\n",
    "        \n",
    "\n",
    "        return res\n",
    "\n",
    "        \n",
    "            \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = [[root, 'null']]\n",
    "        re = []\n",
    "        m = 0\n",
    "        while stack:\n",
    "            root,fa = stack.pop()\n",
    "            root.val = 1\n",
    "            re.append([root, fa])\n",
    "            if root.right:\n",
    "                stack.append([root.right, root])\n",
    "            if root.left:\n",
    "                stack.append([root.left, root])\n",
    "        for root,fa in re[::-1]:\n",
    "            if fa != 'null':\n",
    "                m = max([m, fa.val+root.val])\n",
    "                fa.val = max([fa.val, root.val+1])\n",
    "        return max([m-1, 0])  # 小心路径长度是节点数-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.max = 0\n",
    "    \n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.depth(root)\n",
    "        \n",
    "        return self.max\n",
    "        \n",
    "    def depth(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        l = self.depth(root.left)\n",
    "        r = self.depth(root.right)\n",
    "        '''每个结点都要去判断左子树+右子树的高度是否大于self.max，更新最大值'''\n",
    "        self.max = max(self.max, l+r)\n",
    "        \n",
    "        # 返回的是高度\n",
    "        return max(l, r) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.max = 0\n",
    "    \n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.depth(root)\n",
    "        \n",
    "        return self.max\n",
    "        \n",
    "    def depth(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        l = self.depth(root.left)\n",
    "        r = self.depth(root.right)\n",
    "        '''每个结点都要去判断左子树+右子树的高度是否大于self.max，更新最大值'''\n",
    "        self.max = max(self.max, l+r)\n",
    "        \n",
    "        # 返回的是高度\n",
    "        return max(l, r) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.res = 0\n",
    "        self.maxDepth(root)\n",
    "        return self.res\n",
    "\n",
    "    def maxDepth(self, root):\n",
    "        if not root: return 0\n",
    "        \n",
    "        L = self.maxDepth(root.left)\n",
    "        R = self.maxDepth(root.right)\n",
    "        \n",
    "        self.res = max(self.res, L + R)\n",
    "        return max(L, R) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        maxl, q = 0, [(root)]\n",
    "        nodes = deque()\n",
    "        while q:\n",
    "            p = q.pop(0)\n",
    "            if p.left: q.append(p.left)\n",
    "            if p.right: q.append(p.right)\n",
    "            nodes.appendleft(p)\n",
    "        \n",
    "        for p in nodes:\n",
    "            l = p.left.val if p.left else 0\n",
    "            r = p.right.val if p.right else 0\n",
    "            maxl = max(l + r, maxl)\n",
    "            p.val = max(l, r) + 1\n",
    "        \n",
    "        return maxl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def post_search(self, root: TreeNode):\n",
    "        q = root\n",
    "        stack = []\n",
    "        queue = []\n",
    "        while q or len(stack) > 0:\n",
    "            if q:\n",
    "                stack.append(q)\n",
    "                queue.append(q)\n",
    "                q = q.right\n",
    "            else:\n",
    "                q = stack.pop()\n",
    "                q = q.left\n",
    "\n",
    "        for i in range(len(queue)-1, -1, -1):\n",
    "            q = queue[i]\n",
    "            left = 0 if q.left is None else q.left.val\n",
    "            right = 0 if q.right is None else q.right.val\n",
    "            self.max_path = max(left + right + 1, self.max_path)\n",
    "            q.val = max(left, right) + 1\n",
    "\n",
    "    def diameterOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        self.max_path = 0\n",
    "        self.post_search(root)\n",
    "        return self.max_path-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        p = root\n",
    "        s = []\n",
    "        r = None\n",
    "        root.dept = 0\n",
    "        maxDept = 0\n",
    "\n",
    "        while s or p:\n",
    "            while p:\n",
    "                s.append(p)\n",
    "                p = p.left\n",
    "\n",
    "            t = s[-1] if s else None\n",
    "            if t.right and t.right != r:\n",
    "                p = t.right  # 不是回路\n",
    "            else:\n",
    "                t = s.pop()\n",
    "                r = t\n",
    "                if not (t.left or t.right):\n",
    "                    # 叶子节点\n",
    "                    t.dept = 1\n",
    "\n",
    "                else:\n",
    "                    lDept = t.left.dept if t.left else 0\n",
    "                    rDept = t.right.dept if t.right else 0\n",
    "                    t.dept = max(lDept, rDept) + 1\n",
    "                    maxDept = max(maxDept, lDept+rDept+1)\n",
    "                    p = None\n",
    "\n",
    "        return max(maxDept -1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        def length(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            que = deque([(root, 1)])\n",
    "            while que:\n",
    "                cur, level = que.popleft()\n",
    "                if cur.left:\n",
    "                    que.append((cur.left, level + 1))\n",
    "                if cur.right:\n",
    "                    que.append((cur.right, level + 1))\n",
    "            \n",
    "            return level\n",
    "        \n",
    "        ret = 0\n",
    "        que = deque([root])\n",
    "        while que:\n",
    "            cur = que.popleft()\n",
    "            ret = max(ret, length(cur.left) + length(cur.right))\n",
    "            if cur.left:\n",
    "                que.append(cur.left)\n",
    "            if cur.right:\n",
    "                que.append(cur.right)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:return 0\n",
    "        index=[root]\n",
    "        depth=[]\n",
    "        res=0\n",
    "        while index:\n",
    "            tmp=index.pop()\n",
    "            if not tmp:\n",
    "                tmp=index.pop()\n",
    "                depth1=depth.pop()\n",
    "                depth2=depth.pop()\n",
    "                depth.append(max(depth1,depth2)+1)\n",
    "                # print(tmp.val,depth1,depth2)\n",
    "                res=max(res,depth1+depth2)\n",
    "                continue\n",
    "            index.append(tmp)\n",
    "            index.append(None)\n",
    "            if tmp.right:\n",
    "                index.append(tmp.right)\n",
    "            else:\n",
    "                depth.append(0)\n",
    "            if tmp.left:\n",
    "                index.append(tmp.left)\n",
    "            else:\n",
    "                depth.append(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        #直径可以理解为某个节点的左子树的最大链长加右子树的最大链长加2\n",
    "        #设计一个计算节点最大链长的函数，顺便就可以把直径算出来\n",
    "        # def dfs(node):\n",
    "        #     if not node:\n",
    "        #         return -1 #这里是-1，因为如果是叶子结点的话，max(l_len,r_len)+1就是-1+1为0了\n",
    "        #     l_len = dfs(node.left)\n",
    "        #     r_len = dfs(node.right)\n",
    "        #     return max(l_len,r_len)+1\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return -1 #这里是-1，因为如果是叶子结点的话，max(l_len,r_len)+1就是-1+1为0了\n",
    "            l_len = dfs(node.left)+1 #这样就是考虑整个左边的长度或者整个右边的长度\n",
    "            r_len = dfs(node.right)+1 \n",
    "            nonlocal ans\n",
    "            ans = max(ans,l_len+r_len)\n",
    "            return max(l_len,r_len)\n",
    "        dfs(root) #从根节点开始遍历了每个节点\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 1\n",
    "\n",
    "    def diameterOfBinaryTree(self, root):\n",
    "        def depth(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = depth(node.left)\n",
    "            r = depth(node.right)\n",
    "            self.ans = max(self.ans, l + r + 1)\n",
    "            return max(l, r) + 1\n",
    "        depth(root)\n",
    "        return self.ans-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        last_visit = None \n",
    "        st = []\n",
    "        max_val = 0\n",
    "        while(st or root):\n",
    "            while(root):\n",
    "                st.append(root)\n",
    "                root = root.left\n",
    "            root = st.pop()\n",
    "            if root.right is None or root.right == last_visit:\n",
    "                lv = root.left.val if root.left else 0 \n",
    "                rv = root.right.val if root.right else 0 \n",
    "                max_val = max(max_val,1+lv+rv)\n",
    "                root.val = max(lv,rv) + 1\n",
    "                last_visit = root\n",
    "                root = None\n",
    "                continue\n",
    "            st.append(root)\n",
    "            root = root.right\n",
    "        return max_val -1 if max_val>0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        #左节点最大层级+右节点最大层级,但是有可能不走跟节点，所以要把每个子节点当成跟节点操作一遍，最后取max\n",
    "        ans = []\n",
    "\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        queue1 = [root.left] if root.left else []\n",
    "        queue2 = []\n",
    "        while queue1:\n",
    "            temp = queue1.pop()\n",
    "            ans.append(self.getMaxDistance(temp))\n",
    "            if temp.left:\n",
    "                queue2.append(temp.left)\n",
    "            if temp.right:\n",
    "                queue2.append(temp.right)\n",
    "            if not queue1:\n",
    "                left += 1\n",
    "                if len(queue2)==0:\n",
    "                    break\n",
    "                queue1.extend(queue2)\n",
    "                queue2 = []\n",
    "\n",
    "        queue1 = [root.right] if root.right else []\n",
    "        queue2 = []                \n",
    "        while queue1:\n",
    "            temp = queue1.pop()\n",
    "            ans.append(self.getMaxDistance(temp))\n",
    "            if temp.left:\n",
    "                queue2.append(temp.left)\n",
    "            if temp.right:\n",
    "                queue2.append(temp.right)\n",
    "            if not queue1:\n",
    "                right += 1                \n",
    "                if len(queue2)==0:\n",
    "                    break\n",
    "                queue1.extend(queue2)\n",
    "                queue2 = []\n",
    "        ans.append(right+left)\n",
    "        return max(ans)\n",
    "\n",
    "    def getMaxDistance(self,root: Optional[TreeNode]) -> int :\n",
    "                #左节点最大层级+右节点最大层级\n",
    "        left = 0\n",
    "        right = 0\n",
    "\n",
    "        queue1 = [root.left] if root.left else []\n",
    "        queue2 = []\n",
    "        while queue1:\n",
    "            temp = queue1.pop()\n",
    "            if temp.left:\n",
    "                queue2.append(temp.left)\n",
    "            if temp.right:\n",
    "                queue2.append(temp.right)\n",
    "            if not queue1:\n",
    "                left += 1\n",
    "                if len(queue2)==0:\n",
    "                    break\n",
    "                queue1.extend(queue2)\n",
    "                queue2 = []\n",
    "\n",
    "        queue1 = [root.right] if root.right else []\n",
    "        queue2 = []                \n",
    "        while queue1:\n",
    "            temp = queue1.pop()\n",
    "            if temp.left:\n",
    "                queue2.append(temp.left)\n",
    "            if temp.right:\n",
    "                queue2.append(temp.right)\n",
    "            if not queue1:\n",
    "                right += 1                \n",
    "                if len(queue2)==0:\n",
    "                    break\n",
    "                queue1.extend(queue2)\n",
    "                queue2 = []\n",
    "        return right+left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        recd=defaultdict(int)\n",
    "        stack,ans=[root],0\n",
    "        while stack:\n",
    "            node=stack.pop()\n",
    "            if node:\n",
    "                stack.append(node)\n",
    "                stack.append(None)\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "            else:\n",
    "                node=stack.pop()\n",
    "                recd[node]=1+max(recd[node.left],recd[node.right])\n",
    "                ans=max(ans,recd[node.left]+recd[node.right])\n",
    "        return ans\n",
    "        '''\n",
    "        def hight(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return 1+max(hight(root.left),hight(root.right))\n",
    "        def path(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            if not root.left and root.right:\n",
    "                return 0\n",
    "            leng=hight(root.left)+hight(root.right)\n",
    "            return max(leng,path(root.left),path(root.right))\n",
    "        return path(root)\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "         ans = 0\n",
    "         def dfs(node):\n",
    "             if node is None:\n",
    "                 return -1\n",
    "             l_len = dfs(node.left)\n",
    "             r_len = dfs(node.right)\n",
    "             nonlocal ans\n",
    "             ans = max(ans, l_len + r_len + 2)\n",
    "             return max(l_len, r_len) + 1\n",
    "         dfs(root)\n",
    "         return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        \n",
    "        lDeep = deepOfTree(root.left)\n",
    "        rDeep = deepOfTree(root.right)\n",
    "        diameter = lDeep + rDeep\n",
    "        leftDiamater = self.diameterOfBinaryTree(root.left)\n",
    "        rightDiamater = self.diameterOfBinaryTree(root.right)\n",
    "        return max(diameter, leftDiamater, rightDiamater)\n",
    "\n",
    "def deepOfTree(root: Optional[TreeNode]) -> int:\n",
    "    if root == None:\n",
    "        return 0\n",
    "\n",
    "    lDeep = deepOfTree(root.left)\n",
    "    rDeep = deepOfTree(root.right)\n",
    "    return max(lDeep, rDeep) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            self.res = max(self.res,l+r+1)\n",
    "            return max(l,r)+1\n",
    "        dfs(root)\n",
    "        return self.res-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        diameter=0\n",
    "        def height(node):\n",
    "            nonlocal diameter\n",
    "            if len(node.children)==0:\n",
    "                return 0\n",
    "            max_height_1,max_height_2=0,0\n",
    "            for child in node.children:\n",
    "                parent_height=height(child)+1\n",
    "                if parent_height>max_height_1:\n",
    "                    max_height_1,max_height_2=parent_height,max_height_1\n",
    "                elif parent_height>max_height_2:\n",
    "                    max_height_2=parent_height\n",
    "            distance=max_height_1+max_height_2\n",
    "            diameter=max(diameter,distance)\n",
    "            return max_height_1\n",
    "        height(root)\n",
    "        return diameter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "\n",
    "        def height(node):\n",
    "            if len(node.children) == 0:\n",
    "                return 0\n",
    "            \n",
    "            nonlocal ans\n",
    "\n",
    "            maxHeight1, maxHeight2 = 0, 0\n",
    "            for child in node.children:\n",
    "                parentHeight = height(child) + 1\n",
    "                if parentHeight > maxHeight1:\n",
    "                    maxHeight1, maxHeight2 = parentHeight, maxHeight1\n",
    "                elif parentHeight > maxHeight2:\n",
    "                    maxHeight2 = parentHeight\n",
    "            \n",
    "            distance = maxHeight1 + maxHeight2\n",
    "            ans = max(ans, distance)\n",
    "\n",
    "            return maxHeight1\n",
    "        \n",
    "        height(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # time complexity: O(n), 通过递归一次且仅一次枚举树中的每个节点\n",
    "        # space complexity: O(n), 使用了递归，这将在函数调用堆栈中消耗额外的内存。在最坏的情况下，所有的节点都在一条路径上链接起来，递归将叠加n次\n",
    "\n",
    "        def height(node):\n",
    "            if len(node.children) == 0 or not node:\n",
    "                return 0\n",
    "            \n",
    "            max_height1 = 0\n",
    "            max_height2 = 0\n",
    "            for child in node.children:\n",
    "                parent_height = height(child) + 1          \n",
    "                max_height1, max_height2 = sorted([max_height1, max_height2, parent_height], reverse=True)[:2]\n",
    "\n",
    "            distance = max_height1 + max_height2\n",
    "            self.max_diameter = max(self.max_diameter, distance)\n",
    "            return max_height1\n",
    "\n",
    "        self.max_diameter = 0\n",
    "        height(root)\n",
    "        return self.max_diameter\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ret = 0\n",
    "        def dfs(node):\n",
    "            nonlocal ret\n",
    "            if not node:\n",
    "                return 0 \n",
    "            cmax1, cmax2 = 0, 0\n",
    "            for nei in node.children:\n",
    "                curr = dfs(nei)\n",
    "                if curr > cmax1:\n",
    "                    cmax2 = cmax1\n",
    "                    cmax1 = curr\n",
    "                elif curr > cmax2:\n",
    "                    cmax2 = curr\n",
    "            ret = max(ret, cmax1 + cmax2)\n",
    "\n",
    "            return cmax1 + 1\n",
    "\n",
    "        dfs(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            x_len = 0\n",
    "            for child in node.children:\n",
    "                y_len = dfs(child) + 1\n",
    "                self.res = max(self.res, x_len + y_len)\n",
    "                x_len = max(x_len, y_len)\n",
    "            return x_len\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        diameter = 0\n",
    "\n",
    "        def height(node):\n",
    "            nonlocal diameter\n",
    "\n",
    "            if not node.children: return 0\n",
    "\n",
    "            max1, max2 = 0, 0\n",
    "            for child in node.children:\n",
    "                parent_height = height(child) + 1\n",
    "                if parent_height > max1:\n",
    "                    max1, max2 = parent_height, max1\n",
    "                elif parent_height > max2:\n",
    "                    max2 = parent_height\n",
    "            distance = max1 + max2\n",
    "            diameter = max(diameter, distance)\n",
    "\n",
    "            return max1\n",
    "\n",
    "        height(root)\n",
    "        return diameter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.res = 0\n",
    "        self.dfs(root)\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, root): #  返回这个点往下最长单链的长度，同时求最大直径\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.children:\n",
    "            return 1\n",
    "        lengths = []\n",
    "        for child in root.children:\n",
    "            lengths.append(self.dfs(child))\n",
    "        lengths.sort()\n",
    "        if len(lengths) == 1:\n",
    "            self.res = max(self.res, lengths[0])\n",
    "        else:\n",
    "            self.res = max(self.res, lengths[-1] + lengths[-2])\n",
    "        return lengths[-1] + 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    # T: O(n), S: O(n)\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.res = 0\n",
    "        # the length of the longest path starting from root\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            max1, max2 = 0, 0\n",
    "            for adj in root.children:\n",
    "                tmp = dfs(adj) + 1\n",
    "                if tmp > max1:\n",
    "                    max2 = max1\n",
    "                    max1 = tmp\n",
    "                elif tmp > max2:\n",
    "                    max2 = tmp\n",
    "            self.res = max(self.res, max1 + max2)\n",
    "            return max1\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.res = 0\n",
    "        \n",
    "        def recur(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            temp1, temp2 = 0, 0\n",
    "            for child in root.children:\n",
    "                temp = recur(child)\n",
    "                temp1, temp2 = max(temp1, temp), min(temp1, max(temp2, temp))\n",
    "                \n",
    "            self.res = max(self.res, temp1 + temp2)\n",
    "            return max(temp1, temp2) + 1\n",
    "        \n",
    "        recur(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.res = 0\n",
    "        # the length of the longest path starting from root\n",
    "        def dfs(root):\n",
    "            if not root: return 0\n",
    "            max1, max2 = 0, 0\n",
    "            for adj in root.children:\n",
    "                tmp = dfs(adj) + 1\n",
    "                if tmp > max1:\n",
    "                    max2 = max1\n",
    "                    max1 = tmp\n",
    "                elif tmp > max2:\n",
    "                    max2 = tmp\n",
    "            self.res = max(self.res, max1 + max2)\n",
    "            return max1\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.dm = 0\n",
    "\n",
    "        def getMaxLength(node: 'Node') -> int:\n",
    "            max1, max2 = 0, 0\n",
    "            for child in node.children:\n",
    "                length = getMaxLength(child) + 1\n",
    "                if length > max1:\n",
    "                    max2 = max1\n",
    "                    max1 = length\n",
    "                elif length > max2:\n",
    "                    max2 = length\n",
    "            self.dm = max(max1+max2, self.dm)\n",
    "            return max1\n",
    "\n",
    "        \n",
    "        getMaxLength(root)\n",
    "        return self.dm\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "                \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: Node) -> int:\n",
    "        return self.answer_1(root)\n",
    "\n",
    "    def answer_1(self, root):\n",
    "        result = 0\n",
    "\n",
    "        def _dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            if not node.children:\n",
    "                return 1\n",
    "\n",
    "            child_count = len(node.children)\n",
    "\n",
    "            max1 = max2 = 0\n",
    "            memo = [0] * child_count\n",
    "\n",
    "            for index in range(child_count):\n",
    "                val = _dfs(node.children[index])\n",
    "\n",
    "                memo[index] = val\n",
    "\n",
    "                if val > max1:\n",
    "                    max1, max2 = val, max1\n",
    "                elif val > max2:\n",
    "                    max2 = val\n",
    "            nonlocal result\n",
    "            result = max(result, max1 + max2)\n",
    "            return max1 + 1\n",
    "\n",
    "        _dfs(root)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans = [0]\n",
    "        def dfs(n):\n",
    "            if len(n.children) == 0:\n",
    "                return 1\n",
    "\n",
    "            res = [0]\n",
    "            for c in n.children:\n",
    "                res.append(dfs(c))\n",
    "            res = sorted(res)\n",
    "            ans[0] = max(ans[0], res[-1]+res[-2])\n",
    "            return res[-1]+1\n",
    "\n",
    "        dfs(root)\n",
    "        return ans[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        lens = [0 for _ in root.children]\n",
    "        for idx, children in enumerate(root.children):\n",
    "            if children is not None:\n",
    "                lens[idx] = self.dfs(children) + 1\n",
    "        tmp_ans = max(lens + [0])\n",
    "        for i in range(len(root.children)):\n",
    "            for j in range(i + 1, len(root.children)):\n",
    "                tmp_ans = max(tmp_ans, lens[i] + lens[j])\n",
    "        self.ans = max(self.ans, tmp_ans)\n",
    "        if len(lens) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return max(lens)\n",
    "\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.ans = 0\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        ans=0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            first=0\n",
    "            second=0\n",
    "            for nxt in node.children:\n",
    "                l=dfs(nxt)\n",
    "                if l>first:\n",
    "                    second=first\n",
    "                    first=l\n",
    "                elif l>second:\n",
    "                    second=l\n",
    "            nonlocal ans\n",
    "            ans=max(ans,first+second)\n",
    "            return first+1\n",
    "        dfs(root)\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        result = 0\n",
    "\n",
    "        def update(max1, max2, val):\n",
    "            if val >= max1:\n",
    "                max2 = max1\n",
    "                max1 = val\n",
    "            elif val >= max2:\n",
    "                max2 = val\n",
    "            return max1, max2\n",
    "        \n",
    "        def dfs(root):\n",
    "            nonlocal result\n",
    "            if root is None:\n",
    "                return 0\n",
    "            max1, max2 = 0, 0\n",
    "            for it in root.children:\n",
    "                val = dfs(it)\n",
    "                max1, max2 = update(max1, max2, val)\n",
    "            result = max(result, max1 + max2)\n",
    "            return max1 + 1\n",
    "        \n",
    "        dfs(root)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        self.ans = 0\n",
    "        \n",
    "        def dfs(root):\n",
    "            d = 0\n",
    "            for i in root.children:\n",
    "                tmp = dfs(i)\n",
    "                self.ans = max(self.ans, d + tmp + 1)\n",
    "                d = max(d, tmp + 1)\n",
    "            return d\n",
    "        \n",
    "        dfs(root)\n",
    "\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "from heapq import nlargest\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def search(root): # -> path_sgl:int, path_dbl:int\n",
    "            if (root is None) or (len(root.children)==0):\n",
    "                return 0, 0\n",
    "            sgl_list, dbl_list =[], []\n",
    "            for c in root.children:\n",
    "                c_sgl, c_dbl = search(c)\n",
    "                sgl_list.append(c_sgl)\n",
    "                dbl_list.append(c_dbl)\n",
    "\n",
    "            if len(sgl_list)>1:\n",
    "                top2sgl = nlargest(2, sgl_list)\n",
    "            else:\n",
    "                top2sgl = [-1,-1]\n",
    "            \n",
    "            return max(sgl_list) +1, max(max(dbl_list), sum(top2sgl)+2)\n",
    "        \n",
    "        path_sgl, path_dbl = search(root)\n",
    "\n",
    "        return max(path_dbl, path_sgl)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            m1 = m2 = 0\n",
    "            if not root:\n",
    "                return 0\n",
    "            for child in root.children:\n",
    "                depth = dfs(child)\n",
    "                if depth > m1:\n",
    "                    m2, m1 = m1, depth\n",
    "                elif depth > m2:\n",
    "                    m2 = depth\n",
    "            res = max(res, m1+m2)\n",
    "            return max(m1, m2)+1\n",
    "\n",
    "        res = 0\n",
    "        dfs(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        ans=0\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            if x is None:\n",
    "                return 0\n",
    "            #巧妙迭代,求子树中距离最大的两条路径之和\n",
    "            max_len=0\n",
    "            for y in x.children:\n",
    "                nex=dfs(y)\n",
    "                ans=max(ans,nex+max_len)\n",
    "                max_len=max(max_len,nex)\n",
    "            return max_len+1\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root: return 0\n",
    "            res = [0, 0]\n",
    "            for node in root.children:\n",
    "                res.append(dfs(node))\n",
    "            res.sort(reverse = True)\n",
    "            ans = max(ans, res[0] + res[1])\n",
    "            return 1 + res[0]\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def search(node):\n",
    "            paths, depths = [], [-1, -1]\n",
    "            for child in node.children:\n",
    "                max_path, max_depth = search(child)\n",
    "                paths.append(max_path)\n",
    "                heapq.heappushpop(depths, max_depth)\n",
    "            paths.append(sum(depths) + 2)\n",
    "            return max(paths), max(depths) + 1\n",
    "        ret, _ = search(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\"\"\"\"\"\"\"\"\"\n",
    "# 节点的定义。\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\"\"\"\"\"\"\"\"\"\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        diameter = 0\n",
    "\n",
    "        def height(node):\n",
    "\n",
    "            nonlocal diameter\n",
    "\n",
    "            if len(node.children) == 0:\n",
    "                return 0\n",
    "\n",
    "            # 选择顶部的两个高度\n",
    "            max_height_1, max_height_2 = 0, 0\n",
    "            for child in node.children:\n",
    "                parent_height = height(child) + 1\n",
    "                if parent_height > max_height_1:\n",
    "                    max_height_1, max_height_2 = parent_height, max_height_1\n",
    "                elif parent_height > max_height_2:\n",
    "                    max_height_2 = parent_height\n",
    "\n",
    "            # 计算两个最远的叶节点之间的距离。\n",
    "            distance = max_height_1 + max_height_2\n",
    "            diameter = max(diameter, distance)\n",
    "\n",
    "            return max_height_1\n",
    "\n",
    "        height(root)\n",
    "        return diameter\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = [0]\n",
    "        self._traverse(root, res)\n",
    "        return res[0] - 1\n",
    "\n",
    "    \n",
    "    def _traverse(self, root, res):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        max_len = 0\n",
    "        second_max_len = 0\n",
    "        if root.children is not None:\n",
    "            for child in root.children:\n",
    "                c_max_len = self._traverse(child, res)\n",
    "\n",
    "                if c_max_len >= max_len:\n",
    "                    second_max_len = max_len\n",
    "                    max_len = c_max_len\n",
    "                elif c_max_len > second_max_len:\n",
    "                    second_max_len = c_max_len\n",
    "        \n",
    "        cur_leaf_to_leaf_dia = max_len + second_max_len + 1\n",
    "\n",
    "        res[0] = max(cur_leaf_to_leaf_dia, res[0])\n",
    "\n",
    "        return max_len + 1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "        def dfs(root):\n",
    "            nonlocal ans\n",
    "            if not root: return 0\n",
    "            res = []\n",
    "            for node in root.children:\n",
    "                res.append(dfs(node))\n",
    "            res = res + [0, 0]\n",
    "            res.sort(reverse = True)\n",
    "            ans = max(ans, res[0] + res[1])\n",
    "            return 1 + res[0]\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        diameter = 0\n",
    "\n",
    "        def maxDepth(node, curr_depth):\n",
    "            nonlocal diameter\n",
    "\n",
    "            if len(node.children) == 0:\n",
    "                return curr_depth\n",
    "            \n",
    "            max_depth_1, max_depth_2 = curr_depth, 0\n",
    "            for child in node.children:\n",
    "                depth = maxDepth(child, curr_depth + 1)\n",
    "                if depth > max_depth_1:\n",
    "                    max_depth_1, max_depth_2 = depth, max_depth_1\n",
    "                elif depth > max_depth_2:\n",
    "                    max_depth_2 = depth\n",
    "\n",
    "            distance = max_depth_1 + max_depth_2 - 2 * curr_depth\n",
    "            diameter = max(diameter, distance)\n",
    "\n",
    "            return max_depth_1\n",
    "        maxDepth(root, 0)\n",
    "        return diameter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal maxlen\n",
    "            if not node:\n",
    "                return 0\n",
    "            if not node.children:\n",
    "                return 1\n",
    "            cur_length = []\n",
    "            for i in node.children:\n",
    "                cur_length.append(dfs(i))\n",
    "            cur_length = sorted(cur_length,reverse=True)\n",
    "            maxlen = max(maxlen,sum(cur_length[:2]))\n",
    "            return cur_length[0]+1\n",
    "        maxlen=0\n",
    "        dfs(root)\n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        #树形DP模板题\n",
    "        ans=0\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            if x is None:\n",
    "                return 0\n",
    "            #巧妙迭代,求子树中距离最大的两条路径之和\n",
    "            max_len=0\n",
    "            for y in x.children:\n",
    "                nex=dfs(y)\n",
    "                ans=max(ans,nex+max_len)\n",
    "                max_len=max(max_len,nex)\n",
    "            return max_len+1\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = 0\n",
    "\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            if not node.children:\n",
    "                return 1\n",
    "\n",
    "            \n",
    "            child_count = len(node.children)\n",
    "\n",
    "            dist = [0] * child_count\n",
    "\n",
    "            max_dist = sec_max_dist = 0\n",
    "\n",
    "            for index in range(child_count):\n",
    "                dist[index] = dfs(node.children[index])\n",
    "                if dist[index]> max_dist:\n",
    "                    max_dist, sec_max_dist = dist[index], max_dist\n",
    "                elif dist[index] > sec_max_dist:\n",
    "                    sec_max_dist = dist[index]\n",
    "            nonlocal result\n",
    "            result = max(result, max_dist + sec_max_dist)\n",
    "            return max_dist + 1\n",
    "        dfs(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.maxdist = 0\n",
    "\n",
    "        def DFS(root):\n",
    "            \"\"\"对于每个node，记录一下当前每个子树中距离最远的\n",
    "               返回最深的子树深度\"\"\"\n",
    "            if not root: return 0\n",
    "            if not root.children: return 1\n",
    "\n",
    "            childNum = len(root.children)\n",
    "            dist = [0] * childNum\n",
    "            maxD, secmaxD = 0, 0\n",
    "            for i in range(childNum):\n",
    "                dist[i] = DFS(root.children[i]) #DFS\n",
    "                if dist[i] > maxD: #找最深的两个子树\n",
    "                    maxD, secmaxD = dist[i], maxD\n",
    "                elif dist[i] > secmaxD:\n",
    "                    secmaxD = dist[i]\n",
    "            self.maxdist = max(self.maxdist, maxD + secmaxD) #更新答案\n",
    "            return maxD + 1\n",
    "\n",
    "        DFS(root)\n",
    "        return self.maxdist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        self.max_diameter = 1\n",
    "        def recur(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            len_stack = []\n",
    "            for child in node.children:\n",
    "                heappush(len_stack, -recur(child))\n",
    "            \n",
    "            first = -heappop(len_stack) if len_stack else 0\n",
    "            second = -heappop(len_stack) if len_stack else 0\n",
    "            self.max_diameter = max(self.max_diameter, first+1+second)\n",
    "            return first+1\n",
    "        recur(root)\n",
    "        return self.max_diameter-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def height(root):\n",
    "            if not root.children:\n",
    "                return 0\n",
    "            \n",
    "            first, second = 0, 0\n",
    "            for node in root.children:\n",
    "                cur_height = height(node) + 1\n",
    "                if cur_height > first:\n",
    "                    first, second = cur_height, first\n",
    "                elif cur_height > second:\n",
    "                    second = cur_height\n",
    "\n",
    "            nonlocal res\n",
    "            res = max(res, first+second)\n",
    "\n",
    "            return first\n",
    "        \n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        height(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root) -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.ret = 0\n",
    "        def helper(root) -> int:\n",
    "            if not root:\n",
    "                return 0\n",
    "            \n",
    "            son_pathes = []\n",
    "            for child in root.children:\n",
    "                son_pathes.append(\n",
    "                    helper(child)\n",
    "                )\n",
    "            \n",
    "            sorted_pathes = sorted(son_pathes)\n",
    "            self.ret = max(self.ret, \n",
    "                    1 + sum(sorted_pathes[-2:])\n",
    "                    )\n",
    "\n",
    "            return sorted_pathes[-1] + 1 if len(sorted_pathes) > 0 else 1\n",
    "        \n",
    "        helper(root)\n",
    "        return self.ret - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.ans = 0#创建一个全局变量\n",
    "        def dfs(root):\n",
    "            if not root.children:#递归终止条件 没有下一层返回1 如只有一个根节点 返回值是1。逻辑上是对的。\n",
    "                #print(f'叶节点 {root.val} 第{n}层')\n",
    "                return 1\n",
    "            res = []#创建一个容器，用于保存当前层的往下的最大深度。\n",
    "            for root in root.children:\n",
    "                leve = dfs(root)#接收返回值\n",
    "                res.append(leve)#把树下面的每一层都添加到容器中\n",
    "            #此行递归结束后 容器内所有的节点都接收完毕，没有漏掉一个\n",
    "            if len(res) > 1:#当n叉树有其他节点\n",
    "                r = sorted(res)#排序后取最后2个容器内的数字，就是当前层最深的路线\n",
    "                self.ans = max(self.ans,r[-1]+r[-2])#更新多叉树答案\n",
    "            else:#此树每一层都是一个节点。最大深度也更新入答案。\n",
    "                self.ans = max(self.ans,res[0])#比如有一个节点是每一层都只有一个节点，他有3层。此时我的self.ans 就等于他，但是在他的那一层有别的节点。此时我的答案就更新成上面的路线。排序后的最后2个节点相加。感觉思路没问题啊。  请大佬指教一二。万分感谢！\n",
    "            #print(f'{root.val}当前层 {res}')\n",
    "            return max(res) + 1\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        lens = [0 for _ in root.children]\n",
    "        for idx, children in enumerate(root.children):\n",
    "            if children is not None:\n",
    "                lens[idx] = self.dfs(children) + 1\n",
    "        tmp_ans = max(lens + [0])\n",
    "        for i in range(len(root.children)):\n",
    "            for j in range(i + 1, len(root.children)):\n",
    "                tmp_ans = max(tmp_ans, lens[i] + lens[j])\n",
    "        # print(lens)\n",
    "        self.ans = max(self.ans, tmp_ans)\n",
    "        if len(lens) == 0:\n",
    "            return 0\n",
    "        else:\n",
    "            return max(lens)\n",
    "\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.ans = 0\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        ans=0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            maxLen=0\n",
    "            for nxt in node.children:\n",
    "                nonlocal ans\n",
    "                cur=dfs(nxt)\n",
    "                ans=max(ans,maxLen+cur)\n",
    "                maxLen=max(maxLen,cur)\n",
    "            return maxLen+1\n",
    "        dfs(root)\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def search(node):\n",
    "            max_path, depths = 0, [-1, -1]\n",
    "            for child in node.children:\n",
    "                path, max_depth = search(child)\n",
    "                max_path = max(max_path, path)\n",
    "                heapq.heappushpop(depths, max_depth)\n",
    "            max_path = max(max_path, sum(depths) + 2)\n",
    "            return max_path, max(depths) + 1\n",
    "        ret, _ = search(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.res = 0\n",
    "        def dfs(node):\n",
    "            first = 0\n",
    "            for child in node.children:\n",
    "                second = dfs(child) + 1\n",
    "                self.res = max(self.res, first + second)\n",
    "                first = max(first, second)\n",
    "            return first\n",
    "        dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def search(node):\n",
    "            paths, depths = [], [-1, -1]\n",
    "            for child in node.children:\n",
    "                max_path, max_depth = search(child)\n",
    "                paths.append(max_path)\n",
    "                heapq.heappushpop(depths, max_depth)\n",
    "            paths.append(sum(depths) + 2)\n",
    "            return max(paths), max(depths) + 1\n",
    "        ret, _ = search(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def search(node):\n",
    "            paths, depths = [], [-1, -1]\n",
    "            for child in node.children:\n",
    "                max_path, max_depth = search(child)\n",
    "                paths.append(max_path)\n",
    "                depths.append(max_depth)\n",
    "            depths.sort()\n",
    "            paths.append(sum(depths[-2:]) + 2)\n",
    "            return max(paths), max(depths) + 1\n",
    "        ret, _ = search(root)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:    return 0\n",
    "        maxLen = 0\n",
    "        def dfs(root):\n",
    "            nonlocal maxLen\n",
    "            if not root.children:\n",
    "                return 0\n",
    "            \n",
    "            depth = [dfs(i) for i in root.children]\n",
    "            if len(depth) == 1:\n",
    "                maxLen = max(maxLen, depth[0] + 1)\n",
    "                return depth[0] + 1\n",
    "\n",
    "            fst = snd = -1\n",
    "            for i in depth:\n",
    "                if fst == -1 or fst <= i:   fst, snd = i, fst\n",
    "                elif snd == -1 or snd < i:  snd = i\n",
    "            maxLen = max(maxLen, fst + snd + 2)\n",
    "            return fst + 1\n",
    "\n",
    "        dfs(root)\n",
    "        return maxLen  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if node.children == []:\n",
    "                return 1\n",
    "            l = []\n",
    "            for c in node.children:\n",
    "                l.append(dfs(c))\n",
    "            l.sort(reverse=True)\n",
    "            print(node.val, l)\n",
    "            res = max(res, l[0])\n",
    "            if len(l) > 1 and l[0] + l[1] > res:\n",
    "                res = l[0] + l[1]\n",
    "            return l[0] + 1\n",
    "        dfs(root)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def deepin(node: 'Node') -> int:\n",
    "            if not node:\n",
    "                return 0\n",
    "            if not node.children:\n",
    "                return 1\n",
    "            return max([deepin(child) for child in node.children]) + 1\n",
    "        ans = 0\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                d1 = d2 = 0\n",
    "                node = queue.popleft()\n",
    "                for child in node.children:\n",
    "                    queue.append(child)\n",
    "                    d = deepin(child)\n",
    "                    if d > d1:\n",
    "                        d1, d2 = d, d1\n",
    "                    elif d > d2:\n",
    "                        d2 = d\n",
    "                ans = max(ans, d1 + d2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children if children is not None else []\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def diameter(self, root: 'Node') -> int:\n",
    "        \"\"\"\n",
    "        :type root: 'Node'\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.adjVex = defaultdict(list)             #邻接表\n",
    "        self.dfs(root)                              #初始化邻接表，建图\n",
    "\n",
    "        que = [root]                                #随便选一个点作为起点\n",
    "        visited = set()\n",
    "        visited.add(root)                           #记忆化\n",
    "        cur = root                                  #全局变量，记下第一次BFS的最后一个点\n",
    "        while que:\n",
    "            cur_len = len(que)\n",
    "            for _ in range(cur_len):\n",
    "                cur = que.pop(0)\n",
    "                for nxt in self.adjVex[cur]:\n",
    "                    if nxt not in visited:\n",
    "                        visited.add(nxt)\n",
    "                        que.append(nxt)\n",
    "        visited.clear()\n",
    "        que = [cur]                                 #第一次BFS最后一个点最为第二次BFS的起点\n",
    "        visited.add(cur)                            #记忆化\n",
    "        level = -1                                  #波纹法 记录距离\n",
    "        while que:\n",
    "            cur_len = len(que)\n",
    "            level += 1                          \n",
    "            for _ in range(cur_len):                #波纹法\n",
    "                cur = que.pop(0)\n",
    "                for nxt in self.adjVex[cur]:\n",
    "                    if nxt not in visited:\n",
    "                        visited.add(nxt)\n",
    "                        que.append(nxt)\n",
    "        return level   \n",
    "\n",
    "\n",
    "    def dfs(self, rt: 'Node') -> None:              #初始化邻接表，建图\n",
    "        if not rt:\n",
    "            return \n",
    "        for ch in rt.children:\n",
    "            self.adjVex[rt].append(ch)\n",
    "            self.adjVex[ch].append(rt)\n",
    "\n",
    "            self.dfs(ch)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
